package sort;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
 * 基数排序
 * @author Ranter
 *
 */
public class RadixSort {
	@Test
	public void fun() {
		int[] n = {421, 240, 35, 532, 305, 430, 124};
		radixSort(n);
		for(int i : n) {
			System.out.print(i + " ");
		}
	}
	//实现基数排序 LSD-从最低位开始排 MSD-从最高位开始排
	public void radixSort(int[] data) {
		int maxBin = maxBin(data);
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		for(int i  = 0; i < 10; i ++) {
			list.add(new ArrayList<Integer>());
		}
		for(int i = 0, factor = 1; i < maxBin; factor *= 10, i ++) {
			for(int j = 0; j < data.length; j ++) {
				list.get((data[j]/factor)%10).add(data[j]);
			}
			for(int j = 0, k = 0; j < list.size(); j ++) {
				while(!list.get(j).isEmpty()) {
					data[k] = list.get(j).get(0);
					list.get(j).remove(0);
					k ++;
				}
			}
		}
	}
	//计算数组里元素的最大位数
	public int maxBin(int[] data) {
		int maxLen = 0;
		for(int i = 0; i < data.length; i ++) {
			int size = Integer.toString(data[i]).length();
			maxLen =  size > maxLen ? size : maxLen;
		}
		return maxLen;
	}
}
